/*
 * Copyright (c) 2004-2005 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date:    Mar. 2011
 */

#include "base/intmath.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/btb_new.hh"
#include "cpu/base.hh"

template<class Impl>
BTB<Impl>::BTB(DerivEdgeCPUParams *params)
    : BasePredictor<Impl>(params),
    btb(this, (params->BTBTableMode == "AliasFree") ?
            true : false),
    numEntries(params->BTBEntries),
    blockShiftAmt(params->blockShiftAmt),
    historyLength(params->BTBHistoryLength),
    indexType(UnknownIndexType),
    tableMode(UnknownTableMode)
{
    if (!isPowerOf2(numEntries)) {
        fatal("BTB entries is not a power of 2!");
    }

    if (params->BTBIndexType == "ExitHistory") {
        indexType = ExitHistory;
    } else if (params->BTBIndexType == "TypeHistory") {
        indexType = TypeHistory;
    } else if (params->BTBIndexType == "BinaryHistory") {
        indexType = BinaryHistory;
//    } else if (params->BTBIndexType == "ConBinaryHistory") {
//        indexType = ConBinaryHistory;
    } else if (params->BTBIndexType == "PathHistory") {
        indexType = PathHistory;
    } else if (params->BTBIndexType == "PredicationHistory") {
        indexType = PredicationHistory;
    } else if (params->BTBIndexType == "NoHistory") {
        indexType = NoHistory;
    } else {
        fatal("Unrecognized index type of btb selected.\n");
    }

    if (params->BTBTableMode == "NormalTable") {
        tableMode = NormalTable;
    } else if (params->BTBTableMode == "AliasFree") {
        tableMode = AliasFree;
    } else {
        fatal("Unrecognized table mode of btb selected.\n");
    }

    historyMask = (ULL(0x1) << historyLength) - 1;

    if (tableMode == NormalTable) {
        btb.resize(numEntries, BTBEntry(this));

        for (unsigned i = 0 ; i < numEntries ; ++i) {
            btb[i].target = 0;
            btb[i].hysteresis = false;
            btb[i].valid = false;
        }
    }

    idxMask = numEntries - 1;

    idxLength = floorLog2(numEntries);

    DPRINTF(EdgePredUnit, "BTB initialized with mode: %s\n", 
            (params->BTBIndexType).c_str());
    DPRINTF(EdgePredUnit, "BTB Entries: %i, BTB idx mask: %#x, "
            "BTB idx length: %i, BTB index mode: %s, "
            "BT$ table mode, %s, BTB history length: %i,"
            "BTB history mask: %#x\n",
            numEntries, idxMask, idxLength,
            (params->BTBIndexType).c_str(),
            (params->BTBTableMode).c_str(),
            historyLength,
            historyMask);
}

template<class Impl>
BTB<Impl>::~BTB()
{}

template<class Impl>
void
BTB<Impl>::reset() 
{
    if (tableMode == NormalTable) {
        for(unsigned i = 0; i < numEntries; ++i) {
            btb[i].target = 0;
            btb[i].hysteresis = false;
            btb[i].valid = false;
        }
    } else {
        btb.clear();
    }
}

template<class Impl>
uint64_t
BTB<Impl>::calcIndex(const Addr &PC, std::vector<uint64_t> & hist)
{
    uint64_t index = ULL(-1);

    if (indexType == NoHistory) {

        index = PC >> blockShiftAmt;

    } else if (indexType == ExitHistory) {

        index = (PC >> blockShiftAmt) ^ (hist[ExitHistory] & ULL(0x7));

    } else if (indexType == TypeHistory) {

        index = ((PC >> blockShiftAmt) << 8) |
            (hist[TypeHistory] & ULL(0xFF));

    } else if (indexType == BinaryHistory) {

        index = (PC >> blockShiftAmt) ^
            (hist[BinaryHistory] & historyMask);

//    } else if (indexType == ConBinaryHistory) {

//        index = ((PC >> blockShiftAmt) << historyLength) |
//            (hist[BinaryHistory] & historyMask);

    } else if (indexType == PathHistory) {

        index = ((PC >> blockShiftAmt) << 16) |
            (hist[PathHistory] & ULL(0xFFFF));

    } else if (indexType == PredicationHistory) {

        index = ((PC >> blockShiftAmt)) ^ 
            (hist[PredicationHistory] & ULL(0xFFFFFFFF));

    } else {

        assert(0 && "Unrecognized index type of btb selected.\n");

    }

    if (tableMode != AliasFree) {
        index &= idxMask;
    }

    return index;
}

template<class Impl>
Addr
BTB<Impl>::lookup(const Addr &PC, std::vector<uint64_t> & hist)
{
    uint64_t btb_idx = calcIndex(PC, hist);

    DPRINTF(EdgePredUnit, "Lookup the indirect btb,"
            " get target: %#x\n",
            btb[btb_idx].target);

    // If this entry is not valid, return the PC itself.
    if (!(btb[btb_idx].valid)) {
        return PC;
    }

    Addr target = (btb[btb_idx].target) << blockShiftAmt;

    return target;
}

template<class Impl>
void
BTB<Impl>::update(const Addr &PC, std::vector<uint64_t> & hist, Addr corr_target)
{
    //update btb table.
    unsigned btb_idx =calcIndex(PC, hist);

    Addr old_target = btb[btb_idx].target;
    bool old_hyst = btb[btb_idx].hysteresis;
    Addr target = (corr_target >> blockShiftAmt);

    btb[btb_idx].target = old_hyst ? old_target : target;
    btb[btb_idx].hysteresis = (old_target == target);

    btb[btb_idx].valid = true;

    DPRINTF(EdgePredUnit, "Block [PC = %#x, ehist = %#x, thist = %#x,"
            " bhist = %#x, phist = %#x,"
            " pred_hist = %#x]"
            " BTB updated(old_hyst = %i, hyst = %i,"
            " old target = %#x, target = %#x).\n",
            PC,
            hist[ExitHistory],
            hist[TypeHistory],
            hist[BinaryHistory],
            hist[PathHistory],
            hist[PredicationHistory],
            old_hyst,
            btb[btb_idx].hysteresis,
            old_target,
            btb[btb_idx].target);
}

